class Heap<T>{
   data: T[] = [];
   private length: number = 0;

   constructor(arr:T[]= []){
     this.buildHeap(arr)
   }

   // 私有工具方法,将数组中的两个元素交换位置
   private swap(i: number, j: number){
    //    [this.data[i], this.data[j]] = [this.data[j], this.data[i]] // Ts的写法
       const temp = this.data[i]
       this.data[i] = this.data[j];
       this.data[j] = temp;
   }
   // 插入方法
   insert(value:T){
     // 1、将插入的元素放在数组的尾部
     this.data.push(value);
     // 2、将数组的长度加一
     this.length++;
   

     this.heapify_up()

   }
   // 上滤操作
   private heapify_up(){
     // 新插入的元素的索引一定是在数组的最后一个位置
     let index = this.length - 1;
     while(index > 0){
          //找到对应的父节点的索引
          let parentIndex = Math.floor((index-1)/2)
          // 将当前节点的大小和父节点的大小进行比较,如果小于父节点，直接结束循环
          if(this.data[index] <= this.data[parentIndex]){
               break
          }else{
               // 如果当前节点大于父节点，则交换两者数据
               this.swap(index,parentIndex)
               // 更新index下标
               index = parentIndex
          }
     }
   }
   
   // 删除(提取)操作
   extract():T | undefined{
     // 1、判断元素为0或者1的情况
     if(this.length === 0) return undefined;
     if(this.length === 1) {
          this.length -- ;
          return this.data.shift() 
     }

     // 2、提取并且需要返回的最大值
     const topValue = this.data[0];
     // 将数组中的最后一个元素弹出放在第一个位置
     this.data[0] = this.data.pop()!
      //将数组的长度减一，如果想让一个数组的长度为0，则可以通过this.data.length = 0来进行操作
     this.length--;

     //3.1定义索引位置
     this.heapify_down(0)

     // 当前节点的左子节点存在的时候，进行遍历(下滤操作)log n级别的复杂度
 
     return topValue
   }
    // 下滤操作
   private heapify_down(start:number){
     console.log("start",start)
     let index = start;
     while(2 * index +1 < this.length){
          // 3.2找出左右子节点
          let leftChildIndex = 2 * index + 1;
          let rightChildIndex= 2 * index + 2;
          //3.3找到左右子节点较大的值，这里经过上面的while判断左子节点一定是存在的，所以这里让左子节点默认为最大的值
          let lagerIndex = leftChildIndex;
           // 当右子节点存在并且 右子节点的数据大于左子节点的时候，将最大的索引更改为右子节点
          if(rightChildIndex < this.length && this.data[rightChildIndex] > this.data[leftChildIndex]){
               lagerIndex = rightChildIndex
          }
          // 3.4较大的值和index位置进行比较
          if(this.data[index] > this.data[lagerIndex]){
               break
          }
          // 3.5交换位置
          this.swap(index,lagerIndex)
          index = lagerIndex
     }
    }
      

   // 其他操作
   peek():T | undefined {
        return undefined
   }

   size(){
    return this.length
   }

   isEmpty(){
    return this.length == 0
   }
   // 原地建堆(将一个数组直接转为堆结构)，打印出来的数组就是堆结构（）直接在原有数组上进行操作，不需要使用额外的空间
   buildHeap(arr:T[]){
     // 1、使用arr的值 数组/长度
     this.data = arr;
     this.length = arr.length
     
      // 2、从第一个非叶子节点，开始进行下滤操作,下面这个公式是正确的，后面有讲解，之前哪个也能完成
      const start = Math.floor((this.length/2)-1)
      for(let i = start; i >= 0; i--){
          this.heapify_down(i)
      }
   }

}

const arr = [9,11,20,56,23,45]
const heap = new Heap<number>(arr);

// heap.build_heap(arr);

console.log(arr)


export default {}